\documentclass[a4paper,10pt,brazil]{article}
\pagenumbering{arabic}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{latexsym}
\usepackage{indentfirst}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{graphics}
\usepackage{textcomp}
\usepackage{listings}
\usepackage{hyphenat}

\lstset{
frame=trbL,                 % adds a frame around the code
numbers=left,
breaklines=true,
basicstyle=\footnotesize,
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
tabsize=2,                  % sets default tabsize to 2 spaces
backgroundcolor=\color[rgb]{0.97,0.97,0.97},  % choose the background color. You must add \usepackage{color}
}
\usepackage{dinossauro}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23,5cm}
\evensidemargin 0cm
\oddsidemargin 0cm
\topmargin 0cm

\hyphenation{au-xi-li-a-res}


\begin{document}
\begin{titlepage}
\begin{center}
\MakeUppercase{\large Universidade Federal de Minas Gerais}\\[0.1cm]
\MakeUppercase{\large Insituto de Ciências Exatas}\\[0.1cm]
\MakeUppercase{\large Departamento de Ciência da Computação}\\[0.1cm]
\MakeUppercase{\large Redes Complexas}

\vfill
\textsc{\Large Trabalho Prático 2}\\[0.5cm]

\hrule \vspace{0.4cm}
{ \huge \bfseries Algoritmo de PageRank}\\[0.4cm]
\hrule \vspace{1.5cm}

{\large
{\bf Professor:} \\
Virgílio A. F. Almeida\\

\vfill

{\bf Alunos:}\\
Leonel Fonseca Ivo\\
Raphael O. S. M. de Faria\\[0.5cm]
{\tt \{leonelf,rapha\}@dcc.ufmg.br}
\vfill
 
\today}
\end{center}
 \thispagestyle{empty}
\end{titlepage}

\pagebreak

\tableofcontents
\newpage

\section{Introdução}

O presente trabalho tem como objetivos a análise de características de uma rede de citações e a classificação dos autores por ordem de influência. Para tal, serão utilizadas uma implementação do algoritmo de PageRank e a classificação pelo \textit{in-degree} de cada nó da rede, cujos resultados serão comparados. A base de dados utilizada neste trabalho possui tamanho moderado, com 1559 nós e mais de 44000 arestas, e está disponível no \textit{site} da disciplina.

A base de dados representa uma rede orientada de citações de publicações científicas, em que os nós representam autores e as arestas representam referências de um autor para outro. Para essa base de dados não foi necessário nenhum tipo de filtragem para remoção de linhas inconsistentes com o formato ou filtragem de autores com nomes sem sentido.

Para a implementação dos algoritmos, utilizou-se \textit{scripts} em \textit{shell} para extração de características da rede como separação do maior componente conectado, e scripts em \textit{python} para a implementação dos algoritmos de classificação por PageRank e pelo \textit{in-degree} dos nós. Utilizou-se, ainda, a ferramenta de manipulação de grafos \textit{Pajek} para auxiliar na extração de algumas das características da rede.

Para facilitar o desenvolvimento deste trabalho, utilizou-se um controle de versão tendo o \textit{Google Code} como repositório. Todo o trabalho pode ser acessado pelo \textit{link} disponibilizado nas referências deste trabalho.

% \renewcommand{\labelenumi}{\textbf{\alph{enumi}}}

\section{Resolução dos Exercícios}

A listagem de todos os códigos-fonte utilizados na resolução dos problemas encontram-se no Apêndice desse documento.

\subsection{Exercício 1}

A extração das características da rede foi feita utilizando-se a ferramenta de manipulação de grafos \textit{Pajek}. A seguir descreve-se com detalhes como realizou-se a extração de cada uma das características da rede.

As duas primeiras características da rede, assim como seu grau médio, podem ser obtidas utilizando-se o menu \texttt{Info -> Network -> General} do Pajek, cuja saída é mostrada na Figura \ref{infoGeral}.

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/info_geral.png}
 \caption{Informação geral}
 \label{infoGeral}
\end{figure}

\begin{itemize}
  \item \textbf{Número de nodos}: São $1559$ autores (nós) nessa rede. Esse número está disponível também na primeira linha do arquivo contendo a base de dados.
  \item \textbf{Número de arestas}: São $44661$ arestas, correspondendo a 44661 citações, como mostrado na Figura \ref{infoGeral} na linha que indica o número total de linhas.
\end{itemize}

Para obter o diâmetro da rede utilizou-se o menu \texttt{Net -> Path between 2 vertices -> Diameter} do \textit{Pajek}.

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/diametro.png}
 \caption{Diâmetro da rede}
 \label{diametro}
\end{figure}

\begin{itemize}
  \item \textbf{Diâmetro}: O diâmetro dessa rede é 8, como mostrado na Figura \ref{diametro}. Esse valor nos permite verificar a existência do Fenômeno do Mundo Pequeno nessa rede, uma vez que o maior caminho mínimo entre dois vértices alcançáveis é pequeno se comparado ao número de vértices e arestas existentes no grafo.
\end{itemize}

\begin{itemize}
  \item \textbf{Grau médio}: O grau médio dos nós do grafo dado pelo \textit{Pajek} é de $57.294$, como mostrado na Figura \ref{infoGeral}. Esse valor foi verificado a partir da criação de dois \textit{scripts}, um para calcular o valor de \textit{in-degree} médio da rede e outro para calcular o \textit{out-degree} médio. Para ambos obteve-se o mesmo valor, $28.647$, que é exatamente a metade do valor encontrado pelo \textit{Pajek}. O mesmo valor para as duas médias era esperado porque toda aresta liga dois vértices, saindo de um e chegando no outro. Logo, toda aresta que sai de um nó é destinada a outro, o que faz com que essas médias sejam iguais. Ambos arquivos estão no apêndice deste documento.
\end{itemize}

\begin{itemize}
  \item \textbf{Tamanho do maior componente conectado}: O tamanho do maior componente conectado foi obtido com o auxílio do menu \texttt{Net -> Components -> Strong} do Pajek. O resultado disso é a geração de um arquivo contendo a identificação do componente ao qual cada vértice pertence. A partir disso, utiliza-se o \textit{script} mostrado abaixo para obter o tamanho do maior componente, o qual é mostrado na sequência.

\begin{codigoMargem} \small 
\$ cat componentes.clu  | sort -n  | uniq -c | tr -s " " | sed 's/^ //g' | head -n 1
1238 1
\end{codigoMargem}

O maior componente conectado dessa rede possui $1238$ vértices, como mostrado acima. Como esse número de vértices representa quase 80\% (79,41\%) do total de vértices do grafo, pode-se dizer que essa rede possui um componente gigante. E, como era de se esperar, a rede possui apenas esse componente gigante. Entretanto, observou-se também que praticamente todos os nós que não pertencem a esse componente gigante são nós desconectados do grafo, sem conexão com nenhum outro, o que é uma peculiaridade dessa rede.
\end{itemize}

Os gráficos gerados para o cálculo do expoente da Lei de Potências das três próximas características foram feitos utilizando-se o \textit{gnuplot}. Foram também utilizados \textit{scripts} para colocar os arquivos gerados pelo Pajek - com os \textit{in-degrees}, \textit{out-degrees} e \textit{total degrees statistics} - em um formato aceito pelo \textit{gnuplot}. As regressões foram realizadas para a função $f(x) = ax^b + c$.

\begin{itemize}
  \item \textbf{Expoente do Lei de Potências do \textit{in-degree}}:

O \textit{script} usado para este caso é mostrado abaixo.

\begin{codigoMargem} \small
cat in_degree.clu | sort -n | uniq -c | sed "s/^ *\textbackslash([0-9]*\textbackslash)/\textbackslash1/g" | awk '\{print $2 " " $1\}'
\end{codigoMargem}

O gráfico gerado é mostrado na Figura \ref{indegree}. Já na Figura \ref{expoenteIndegree} mostra-se o valor do expoente para a Lei de Potências do \textit{in-degree} (parâmetro $b$), que é $-0.488$

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/in_degree_grafico.png}
 \caption{In-Degree}
 \label{indegree}
\end{figure}

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/expoente_in_degree.png}
 \caption{Expoente In-Degree}
 \label{expoenteIndegree}
\end{figure}

  \item \textbf{Expoente do Lei de Potências do \textit{out-degree}}:

O \textit{script} usado neste caso é mostrado abaixo.

\begin{codigoMargem} \small
cat out_degree.clu | sort -n | uniq -c | sed "s/^ *\textbackslash([0-9]*\textbackslash)/\textbackslash1/g" | awk '{print $2 " " $1}'
\end{codigoMargem}

O gráfico gerado é mostrado na Figura \ref{outdegree}. Na Figura \ref{expoenteOutdegree} mostra-se o valor do expoente para a Lei de Potências do \textit{out-degree} (parâmetro $b$), que é $-0.107$

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/out_degree_grafico.png}
 \caption{Out-Degree}
 \label{outdegree}
\end{figure}

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/expoente_out_degree.png}
 \caption{Expoente Out-Degree}
 \label{expoenteOutdegree}
\end{figure}

  \item \textbf{Expoente do Lei de Potências do \textit{total degree statistics}}:

Para o caso da estatísticas gerais dos graus, o \textit{script} utilizado é o mostrado abaixo.

\begin{codigoMargem} \small
cat all_degree.clu | sort -n | uniq -c | sed "s/^ *\textbackslash([0-9]*\textbackslash)/\textbackslash1/g" | awk '{print $2 " " $1}'
\end{codigoMargem}

O gráfico gerado é mostrado na Figura \ref{alldegree}. Na Figura \ref{expoenteAlldegree} mostra-se o valor do expoente para a Lei de Potências do \textit{out-degree} (parâmetro $b$), que é $-0.025$

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/all_degree_grafico.png}
 \caption{All-Degree}
 \label{alldegree}
\end{figure}

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/expoente_all_degree.png}
 \caption{Expoente All-Degree}
 \label{expoenteAlldegree}
\end{figure}

\end{itemize}
\newpage
\begin{itemize}
  \item \textbf{Coeficiente de clusterização}: Para o cálculo dos coeficientes de clusterização dos nós da rede utilizou-se o menu \texttt{Net -> Vector -> Clustering Coefficients -> CC1}, o qual gera uma lista com os coeficientes de clusterização de cada nó da rede. A Figura \ref{clusterizacao} exibe os coeficientes dos 10 primeiros nós.

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/clusterizacao.png}
 \caption{Coeficientes de Clusterização}
 \label{clusterizacao}
\end{figure}

Calculou-se também o coeficiente médio da rede com o auxílio do script mostrado abaixo, o qual deu como resultado um coeficiente médio de $0.1551$.

\begin{codigoMargem} \small
echo "scale=4;  (\$(cat ../dados/cluesterizacao.vec | tr '/n' '+' | sed 's/+\$//') ) / 
                 \$(cat ../dados/cluesterizacao.vec | wc -l) " | bc
\end{codigoMargem}

\newpage
  \item \textbf{Caminho mínimo médio}: O caminho mínimo médio da rede é de $2.774$ e foi calculado utilizando-se o menu \texttt{Net -> Path between 2 vertices -> Distribution of Distances -> From All Vertices}, cujo resultado é mostrado na Figura \ref{caminhoMinimoMedio}. O cálculo é feito levando-se em conta apenas vértices alcançáveis, ou seja, vértices dentro de um mesmo componente conectado, uma vez que vértices inalcançáveis tem distância infinita.

\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.52]{../imagens/caminho_minimo_medio.png}
 \caption{Caminho mínimo médio}
 \label{caminhoMinimoMedio}
\end{figure}

Esse valor de caminho mínimo médio está dentro do esperado, uma vez que é menor que o diâmetro da rede.

\end{itemize}

\subsection{Exercício 2}

    \textbf{PageRank adaptado} \newline

A implementação do algoritmo de PageRank está listada no apêndice deste trabalho. Optou-se por rodar o algoritmo do PageRank com 50 iterações.

A seguir são mostrados os 10 autores mais influentes de acordo com o calculado por esse algortimo, em ordem decrescente de influência. A saída exibida mostra, além dos nomes dos autores, um vetor com as seguintes três informações: identificador do autor, seu \textit{out-degree} e o valor de seu \textit{ranking}.
\newline

\begin{codigoMargem}
[831, 2, 0.033901461437125968]
"Fisher, David"

[510, 1, 0.019846708305899779]
"McCarthy, Joseph"

[466, 1, 0.018261999913858674]
"Woods, William A."

[1489, 1, 0.017033803755582375]
"Peterson, Jill"

[345, 1, 0.012093552815912168]
"Wasow, Thomas"

[231, 1, 0.0082367289793145743]
"Sturtevant, Dean G."

[240, 1, 0.0041418846570464235]
"Yu, Edmund S."

[1351, 1, 0.004129025364130086]
"Paik, Woojin"

[235, 1, 0.002541810656263071]
"Pellom, Bryan"

[951, 1, 0.0020779888994968483]
"Shinn, Sandy"
\end{codigoMargem}

Os valores de \textit{in-degree} para cada um desses 10 autores mais influentes são, respectivamente: 31, 34, 15, 24, 28, 9, 8, 9, 5 e 3. Esses valores servirão para a análise comparativa desse algoritmo de classificação com a classificação por \textit{in-degree}.
\newline

    \textbf{Classificação por \textit{in-degree}} \newline

A implementação do algoritmo de classificação pelo \textit{in-degree} também está listada no apêndice deste trabalho. 

A seguir são mostrados os 10 autores mais influentes de acordo com o calculado por esse algortimo, em ordem decrescente de influência. A saída exibida mostra, além dos nomes dos autores, um vetor com as seguintes duas informações: identificador do autor e seu \textit{in-degree}.
\newline

\begin{codigoMargem}
Rank para inDegree : 
[263, 433]
"Marcus, Mitchell P."

[1470, 430]
"Della Pietra, Vincent J."

[788, 406]
"Church, Kenneth Ward"

[1287, 392]
"Della Pietra, Stephen A."

[42, 380]
"Mercer, Robert L."

[765, 368]
"Santorini, Beatrice"

[380, 351]
"Brown, Peter F."

[695, 344]
"Collins, Michael John"

[1068, 331]
"Grishman, Ralph"

[748, 327]
"Brill, Eric"
\end{codigoMargem}
\newline

    \textbf{Comparação PageRank x \textit{In-degree}}
\newline

Como pode-se notar pela comparação dos resultados, vê-se que os 10 autores mais influentes segundo o PageRank são todos diferentes dos 10 autores mais influentes segundo a classificação por \textit{in-degree}. No caso do PageRank, os 10 autores mais influentes não são aqueles que são mais citados por outros autores, mas sim aqueles que são mais citados por autores mais influentes. A medida de importância, nesse caso, não pode ser somente o número de citações que um autor tem, pois ele pode estar sendo citado por muitos outros autores cujos trabalhos ainda não são muito reconhecidos. O PageRank leva essa medida de importância do nó (autor) em consideração, dividindo a importância desse nó para os nós aos quais ele aponta. Quanto mais importantes são os autores que citam o trabalho de um determinado autor, maior é a nota desse último e, portanto, mais influente ele é.

Essa forma de classificação do PageRank é mais apropriada para esse tipo de classificação porque ele é de manipulação mais difícil que a classificação por \textit{in-degree}. Essa última, por exemplo, permite que a criação de vértices que apontem para um único autor, buscando promovê-lo, subam no ranking de influência. No caso do PageRank, esse tipo de ação não eleva a nota do autor em questão, porque os nós criados não tem importância (a partir da segunda iteração terão nota zero, se não houver ninguem apontando para eles).

\section{Conclusão}

A extração das características da rede e a implementação dos algoritmos de classificação auxiliaram na melhor compreensão do que foi estudado e permitiu verificar a qualidade do algoritmo de PageRank quando contrastado com a classificação por \textit{in-degree}. Nessa comparação, verificou-se que a forma como o PageRank atribui importâncias aos nós do grafo faz com que ele seja menos manipulável do que a classificação por \textit{in-degree}.

Pode-se dizer que o objetivo do trabalho foi cumprido, ao permitir uma comparação prática dos resultados produzidos pelo PageRank quando contrastato com a classificação por \textit{in-degree}. Além disso, foi possível verificar com sucesso as características da rede e a existência de fenômenos como o do Mundo Pequeno e da Lei de Potências.


\newpage
\appendix

\lstset{language=bash,
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
%numbersep=5pt,                  % how far the line-numbers are from the code
%backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
%showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
%showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,	                % adds a frame around the code
tabsize=2,	                % sets default tabsize to 2 spaces
%captionpos=b,                   % sets the caption-position to bottom
%breaklines=true,                % sets automatic line breaking
%breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
%title=\lstname,                 % show the filename of files included with \lstinputlisting; also try caption instead of title
%escapeinside={\%*}{*)}          % if you want to add a comment within your code
extendedchars=true,
inputencoding=utf8
}

\section{Listagem dos \textit{scripts}}

  \subsection{Geração de arquivos auxiliares}
\lstinputlisting[caption=componente.sh]{../src/componente.sh}
\lstinputlisting[caption=cria\_apontadoPor.sh]{../src/cria_apontadoPor.sh}
\lstinputlisting[caption=cria\_relacinados.sh]{../src/cria_relacinados.sh}
\lstinputlisting[caption=in\_degree\_media.sh]{../src/in_degree_media.sh}
\lstinputlisting[caption=out\_degree\_media.sh]{../src/out_degree_media.sh}

  \subsection{Classificação}
\lstinputlisting[caption=pagerank.py]{../src/pagerank.py}
\lstinputlisting[caption=in\_degree\_rank.py]{../src/in_degree_rank.py}

%   \subsection{Geração de gráficos}
% \lstinputlisting[caption=Exercicio 1 item 'a']{../src/exercicio_1_a.gnu}
% \lstinputlisting[caption=Exercicio 1 item 'b']{../src/exercicio_1_b.gnu}
% \lstinputlisting[caption=Exercicio 2]{../src/exercicio_2.gnu}
% \lstinputlisting[caption=Exercicio 3]{../src/exercicio_3.gnu}
% \lstinputlisting[caption=Exercicio 4]{../src/exercicio_4.gnu}

\nocite{*}
\bibliographystyle{plain}
%\bibliographystyle{apalike}
\renewcommand{\refname}{Referências}
\addcontentsline{toc}{section}{Referências}
\bibliography{referencias}

\end{document}
